package com.dragon.redblanktree;

import com.dragon.queue.LinkedListQueue;
import com.dragon.stack.LinkedListStack;

/**
 * @author dragon
 * @version V1.0.0-RELEASE
 * @date 2019/5/26 15:17
 */
public class RBTree<E extends Comparable<E>> {

    /**
     * 二分搜索树的根节点
     */
    private Node<E> root;

    /**
     * 二分搜索树中的节点个数
     */
    private int size;

    private static final boolean RED = true;

    private static final boolean BLANK = false;

    private static class Node<E> {
        E item;
        Node<E> left;
        Node<E> right;
        boolean color;

        public Node(E item, Node<E> left, Node<E> right) {
            this.item = item;
            this.left = left;
            this.right = right;
            color = RED;
        }
    }

    private boolean isRed(Node node) {
        if (node == null) {
            return BLANK;
        }
        return node.color;
    }

    /**
     * 树中元素是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取元素个数
     *
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 添加元素
     *
     * @param e
     */
    public void add(E e) {
        if (root == null) {
            root = new Node<E>(e, null, null);
        } else {
            addRec(e, root);
        }
    }

    /**
     * 向红黑树中添加元素
     *
     * @param e
     */
    public void addElement(E e) {
        root = add(e, root);
        // 最终根节点为黑色节点
        root.color = BLANK;
    }

    /**
     * 将 node 节点进行左旋转
     *
     * @param node
     * @return
     */
    private Node leftRotate(Node node) {
        Node x = node.right;
        // 左旋转
        node.right = x.left;
        x.left = node;

        x.color = node.color;
        node.color = RED;

        return x;
    }

    /**
     * 颜色翻转
     *
     * @param node
     */
    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLANK;
        node.right.color = BLANK;
    }

    /**
     * 右旋转
     *
     * @param node
     * @return
     */
    private Node rightRotate(Node node) {
        Node x = node.left;
        // 右旋转
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = RED;

        return x;
    }

    private Node<E> add(E e, Node<E> node) {
        if (node == null) {
            node = new Node<>(e, null, null);
            size++;
        }
        if (node.item.compareTo(e) > 0) {
            node.left = add(e, node.left);
        } else if (node.item.compareTo(e) < 0) {
            node.right = add(e, node.right);
        } else {
            node.item = e;
        }

        // 如果该节点的左孩子不为红节点,且该节点的右孩子为红节点,则进行左旋转
        if (isRed(node.right) && !isRed(node.left)) {
            // 左旋转
            node = leftRotate(node);
        }
        // 如果该节点的左孩子为红节点,左左孩子也为红节点,则进行右旋转
        if (isRed(node.left) && isRed(node.left.left)) {
            // 右旋转
            node = rightRotate(node);
        }
        // 如果该节点的左右孩子都为红节点
        if (isRed(node.left) && isRed(node.right)) {
            // 进行颜色翻转
            flipColors(node);
        }

        return node;
    }

    /**
     * 添加元素，递归
     *
     * @param e
     * @param node
     */
    private void addRec(E e, Node<E> node) {
        if (node.item.compareTo(e) == 0) {
            return;
        }
        if (node.item.compareTo(e) < 0 && node.right == null) {
            node.right = new Node<E>(e, null, null);
            size++;
            return;
        }
        if (node.item.compareTo(e) > 0 && node.left == null) {
            node.left = new Node<E>(e, null, null);
            size++;
            return;
        }
        if (node.item.compareTo(e) < 0) {
            addRec(e, node.right);
        } else {
            addRec(e, node.left);
        }
    }

    /**
     * 删除元素
     *
     * @param e
     */
    public void remove(E e) {

    }

    /**
     * 是否包含某个元素
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return contains(e, root);
    }

    /**
     * 递归判断是否包含某个元素
     *
     * @param e
     * @param node
     * @return
     */
    private boolean contains(E e, Node<E> node) {
        if (node == null) {
            return false;
        }
        if (node.item.compareTo(e) == 0) {
            return true;
        } else if (node.item.compareTo(e) > 0) {
            return contains(e, node.right);
        } else {
            return contains(e, node.left);
        }
    }

    /**
     * 前序遍历:根节点==》左子树==》右子树
     */
    public void preOrder() {
        System.out.print("前序遍历:");
        preOrder(root);
    }

    private void preOrder(Node<E> node) {
        if (node == null) {
            return;
        }
        //1.先访问根节点
        System.out.print(node.item + " ");
        //2.在访问左子树
        preOrder(node.left);
        //3.在访问右子树
        preOrder(node.right);
    }

    /**
     * 前序遍历非递归的实现方法
     */
    public void preOrderNC() {
        if (isEmpty()) {
            return;
        }
        LinkedListStack<Node<E>> stack = new LinkedListStack<>();
        stack.push(root);
        System.out.print("前序遍历非递归:");
        while (!stack.isEmpty()) {
            Node<E> returnNode = stack.pop();
            System.out.print(returnNode.item + " ");
            if (returnNode.right != null) {
                stack.push(returnNode.right);
            }
            if (returnNode.left != null) {
                stack.push(returnNode.left);
            }
        }
    }

    /**
     * 层序遍历
     */
    public void levelOrder() {
        if (isEmpty()) {
            return;
        }
        System.out.print("层序遍历:");
        LinkedListQueue<Node<E>> queue = new LinkedListQueue<>();
        queue.enqueue(root);
        while (!queue.isEmpty()) {
            Node<E> returnNode = queue.dequeue();
            System.out.print(returnNode.item + " ");
            if (returnNode.left != null) {
                queue.enqueue(returnNode.left);
            }
            if (returnNode.right != null) {
                queue.enqueue(returnNode.right);
            }

        }
    }

    /**
     * 中序遍历：左子树==》根节点==》右子树
     */
    public void midOrder() {
        System.out.print("中序遍历:");
        midOrder(root);
    }

    private void midOrder(Node<E> node) {
        if (node == null) {
            return;
        }
        //1.在访问左子树
        midOrder(node.left);
        //2.先访问根节点
        System.out.print(node.item + " ");
        //3.在访问右子树
        midOrder(node.right);
    }

    /**
     * 后序遍历：左子树==》右子树==》根节点
     */
    public void postOrder() {
        System.out.print("后序遍历:");
        postOrder(root);
    }

    private void postOrder(Node<E> node) {
        if (node == null) {
            return;
        }
        //1.在访问左子树
        postOrder(node.left);
        //2.在访问右子树
        postOrder(node.right);
        //3.先访问根节点
        System.out.print(node.item + " ");
    }

    /**
     * 寻找二分搜索树的最小元素
     *
     * @return
     */
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("binarySearchTree is empty");
        }
        return minimum(root).item;
    }

    /**
     * 返回以node为根的二分搜索树中的最小值所在的节点
     *
     * @param node
     * @return
     */
    private Node<E> minimum(Node<E> node) {
        if (node.left == null) {
            return node;
        }
        return minimum(node.left);
    }

    /**
     * 返回二分搜索树中的最大元素
     *
     * @return
     */
    public E maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("binarySearchTree is empty");
        }
        return maximum(root).item;
    }

    /**
     * 返回以node为根的二分搜索树中的最大值的所在的节点
     *
     * @param node
     * @return
     */
    private Node<E> maximum(Node<E> node) {
        if (node.right == null) {
            return node;
        }
        return maximum(node.right);
    }
}
